package priv.pront.code.lanqiao.competition.course.date0401;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @Description:
 * @Author: pront
 * @Time:2023-04-01 17:58
 */
public class Main {
    static int N;
    static char[][] map;
    static int K;
    static int step;
    static boolean[][][] vis;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, -1, 0, 1 };

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        K = in.nextInt();
        int ans = -1;
        map = new char[N + 2][N + 2];
        vis = new boolean[N + 2][N + 2][11];
        String tempStr = in.nextLine();
        for (int i = 1; i <= N; i++) {
            tempStr = in.nextLine();
            for (int j = 0; j < tempStr.length(); j++) {
                map[i][j + 1] = tempStr.charAt(j);
            }
        }
        Main main = new Main();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(map[1][1] == '.' ? main.new Node(1, 1, 0, 0) : main.new Node(1, 1, 0, K));
        if (map[1][1] == '.') {
            vis[1][1][0] = true;
        } else {
            vis[1][1][K] = true;
        }
        while(!queue.isEmpty()) {
            Node tempNode = queue.poll();
            if(tempNode.x==N&&tempNode.y==N) {
                ans = tempNode.step;
                break;
            }
            for(int i=0;i<4;i++) {
                int x = tempNode.x+dx[i];
                int y = tempNode.y+dy[i];
                if(map[x][y]!='#'&&x>=1&&x<=N&&y>=1&&y<=N) {
                    if(map[x][y]=='X'&&tempNode.invincible>0&&vis[x][y][tempNode.invincible-1]==false) {
                        vis[x][y][tempNode.invincible-1]=true;
                        queue.offer(main.new Node(x,y,tempNode.step+1,tempNode.invincible-1));
                    }else if(map[x][y]=='%'&&vis[x][y][K]==false) {
                        vis[x][y][K]=true;
                        queue.offer(main.new Node(x,y,tempNode.step+1,K));
                    }else if(map[x][y]=='.'&&tempNode.invincible==0&&vis[x][y][0]==false) {
                        vis[x][y][0]=true;
                        queue.offer(main.new Node(x,y,tempNode.step+1,0));
                    }else if(map[x][y]=='.'&&tempNode.invincible>0&&vis[x][y][tempNode.invincible-1]==false) {
                        vis[x][y][tempNode.invincible-1]=true;
                        queue.offer(main.new Node(x,y,tempNode.step+1,tempNode.invincible-1));
                    }
                }
            }
        }
        System.out.println(ans);
    }

    class Node {
        int x;
        int y;
        int step;
        int invincible;

        public Node(int x, int y, int step, int invincible) {
            super();
            this.x = x;
            this.y = y;
            this.step = step;
            this.invincible = invincible;
        }
    }
}
